1. Field of the Invention
The present invention is generally related to digital computers that utilize read and write pointers to access a memory element and more particularly relates to means for checking the validity of the read and write pointers.
2. Description of the Prior Art
A key element in the design of high reliability computer systems is error detection. The term "error detection" refers to the detection of errors within a computer system before the errors adversely affect the arithmetic operations within the computer system. Many of today's computer systems incorporate some form of error detection to achieve improved reliability.
Large scale error detection has proved to be expensive to implement and maintain. In response thereto, many computer designers are limiting the use of error detection to portions of the computer system that can provide the most benefit. Memory elements are historically one place where error detection is targeted. Errors that occur either internal to a memory element or adjacent to the inputs or outputs of a memory element are far more likely to adversely affect the arithmetic operations within the computer system than those that occur in combinational logic. Memory elements must "store" data for later use whereas combinational logic merely operates on data in real time.
A specific type of memory element that is of interest is a memory stack. A memory stack is a number of memory locations that may be accessed via an address bus. A read/write memory stack employs two address busses which are typically called pointers. The read/write memory stack has a read pointer and a write pointer. A memory controller within the computer system may control the read pointer and the write pointer such that only valid data is written to the memory stack and only valid data is read from the memory stack. In a typical system, the memory controller may write one or more data words into a series of address locations using the write pointer. At a later time, the memory controller may read the previously written data elements using the read pointer.
In one type of read/write memory stack, called a first-in-first-out (FIFO) stack, the write pointer is incremented as data is written into the stack. Similarly, when reading the stack, the read pointer is incremented through the same memory locations as the write pointer passed through and in the same order, thus causing the first data element that is written to the FIFO stack to also be the first element that is read from the FIFO stack. The memory controller may not allow the read pointer to be incremented past the write pointer thus preventing invalid data from being read from the memory stack.
The absolute address location that is written or read via the write and read pointers is not important in a FIFO stack configuration. Rather, the relative difference between the write pointer and the read pointer is what defines valid data. The write and read pointers are typically generated by counters whereby the counters have a predetermined width. The width of the counters are selected such that counters have the same number of states as the corresponding memory element. In this way, the counters can be incremented such that the pointer address travels from a zero address to the maximum address of the memory element and then back to the zero address.
The memory controller may provide protection for preventing the write pointer from being incremented into data that has not yet been read. This is termed a "stack full" condition. When a stack full condition is detected, the memory controller must read data from the memory stack before further data can be written into the stack.
One method for providing error detection within a system is termed "parity". Parity is a method for detecting errors whereby one additional "parity bit" is added to each data word in a memory element. For example, in a 16 bit data word, one additional "parity bit" may be added to each data word thereby resulting in a 17 bit data word that must be stored in memory. Parity is defined as either "odd" parity or "even" parity. The parity bit may be set by a parity generator such that the total number of 1's in a data word is an even number for an "even" parity system. Conversely, the parity bit may be set by the parity generator such that total number of 1's in the data word is an odd number for an "odd" parity system. When the data word is later read from the memory, the parity generator regenerates the parity bit for the data word that is read from memory and is compared to the originally stored parity bit. If there is a difference, an error is detected.
A single parity bit per data word can detect if a single data bit in a data word flips from one state to another. However, A single parity bit per data word may not be able to detect if more than one bit within a data word flips from one state to another. For example, if two bits within a data word flip from one state to another, the value of the parity bit of the corrupted data word will remain the same as the value of the parity bit of the originally stored data word. Therefore, one parity bit per data word may only allow the detection of a single bit flip within a given data word. To detect multiple bit flips per data word, various numbers of parity bits must be added to each data word depending on the parity generation technique used. In systems that have large arrays of memory elements with potentially hundreds of thousands of data words, it can readily be seen that the parity technique for detecting errors within a computer system can be costly to implement and can require a relatively high level of overhead.
Another technique for performing error detection in a system is to provide redundancy. Redundancy provides duplicate circuits in critical areas of the computer system. The inputs of a duplicate circuit may be tied to a corresponding input of a primary circuit. The output of the duplicate circuit is then compared to the output of the primary circuit during system operation. If there is a difference, an error flag may be set. When utilizing this technique, it is assumed that if both circuits produce the same result, both circuits are operating properly and therefore no error has occurred.
In some systems, three or more identical circuits are provided and the outputs of the circuits are connected to a voting circuit. The voting circuit compares the outputs of the identical circuits and provides an output that is consistent with the majority of the circuits. With either of these redundancy techniques described above, it is readily apparent that both can be costly to implement and can require a relatively high level of overhead.
The FIFO stack memory element referred to above may employ either the parity technique or the redundancy technique or a combination thereof to provide error detection for the memory element itself. However, a particular concern for this type of memory element is the integrity of the read pointer and the write pointer. If an error occurs on either the read pointer or the write pointer, the error will in all probability be propagated into the computer system. As previously stated, the read and write pointers are typically controlled by a memory controller circuit. It can be critical that the memory controller circuit have error detection designed therein. In a typical system, the read pointer and the write pointer will each be controlled by a counter and other peripheral circuitry.
To detect errors in the read and write pointers, a duplicate set of pointer/counters may be provided in addition to the primary set. When a primary read counter is incremented, a duplicate read counter may also be incremented. Similarly, when a primary write counter is incremented, a duplicate write counter may also be incremented. A first comparator may be coupled to the outputs of the primary and the duplicate read counters and a second comparator may be coupled to the output of the primary and duplicate write counters. If either the first comparator or the second comparator detects that the primary counter differs from the duplicate counter, an error signal may be generated.
Although the error detection methods discussed above may provide some level of error protection, they cannot detect certain classes of errors that may occur on the read and write pointers. For example, if an error condition causes both the primary and duplicate read counters to increment, the error may go undetected. This may not be as unlikely as it first might seem because typically the respective inputs of the primary and duplicate counters are tied together. Therefore if an error occurs on an input signal to the counters, both the primary and duplicate counters may propagate the error. For example, if a glitch occurs on an ENABLE or a COUNT input to the counters, both counters may inadvertently increment. This error may eventually be returned to the computer system in a stack read operation.